#include <gtest/gtest.h>
#include <string>
#include <stack>
#include <unordered_map>

using namespace ::std;

// 栈，先进后出
// 实现时注意细节，特殊情况较多，需要考虑周全
// 第一版实现不理想，重来！！！
unordered_map<char, char> mapBrackets = {
	{'(', ')'}, {'[', ']'}, {'{', '}'}
};

unordered_map<char, bool> mapIsLeft = {
	{'(', true}, {'[', true}, {'{', true},
	{')', false}, {']', false}, {'}', false}
};

class Solution {
public:
    bool isValid(string s) {
		if(s.size() % 2) return false;
		stack<char> leftBrackets;
		for(char c : s) {
			if(mapIsLeft[c]) {
				leftBrackets.push(c);
			} else {
				if(leftBrackets.empty() || mapBrackets[leftBrackets.top()] != c) return false;
				else leftBrackets.pop();
			}
		}
		if(!leftBrackets.empty()) return false;
		return true;
    }
};

class IsValidCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(IsValidCheck, testIsValid_1) {
	string s = "()";
	EXPECT_TRUE(true == solution.isValid(s));
}

TEST_F(IsValidCheck, testIsValid_2) {
	string s = "()[]{}";
	EXPECT_TRUE(true == solution.isValid(s));
}

TEST_F(IsValidCheck, testIsValid_3) {
	string s = "()[(]{}";
	EXPECT_TRUE(false == solution.isValid(s));
}

TEST_F(IsValidCheck, testIsValid_4) {
	string s = "((";
	EXPECT_TRUE(false == solution.isValid(s));
}

TEST_F(IsValidCheck, testIsValid_5) {
	string s = "()()((())";
	EXPECT_TRUE(false == solution.isValid(s));
}

TEST_F(IsValidCheck, testIsValid_6) {
	string s = ")(";
	EXPECT_TRUE(false == solution.isValid(s));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
